#include <iostream>
#include <algorithm>
#include <vector>

using std::cout;
using std::endl;
using std::vector;
// 现有 1 3 5 面值的硬币，如果要凑齐 n 价值，最少需要多少枚硬币

// 定义dp数组
/* int *dp = new int[19]{0}; 

int fun(int n) 
{
    if(dp[n] != 0) return dp[n];
    if(n == 1 || n == 3 || n == 5){
        dp[n] = 1;
        return 1;
    }else if(n == 2 || n == 4){
        dp[n] = 2;
        return 2;
    }else{
        int n1 = fun(n - 1) + 1; // 选取面值 1
        int n2 = fun(n - 3) + 1; // 选取面值 3
        int n3 = fun(n - 5) + 1; // 选取面值 5
        dp[n] = std::min({n1, n2, n3});
        return dp[n];
    }
} */

// 状态转移方程：dp[i] = min(dp[i - vj] + 1);
void minFetch(int *v, int len, int m)
{
    vector<int> dp;
    dp.resize(m + 1);
    dp[0] = 0; // dp[1] = 1, dp[2] = 2, dp[3] = 1, dp[4] = 2, dp[5] = 1;
    for(int i{1}; i <= m; i++){
        dp[i] = i;
        for(int j{}; j < len; j++){
            int min = dp[i];
            if(i >= v[j]){
                if(min > dp[i - v[j]] + 1){
                    min = dp[i - v[j]] + 1;
                }
            }
            dp[i] = min;
        }
    }
    cout << dp[m] << endl;
}

int main(int args, char *argv[])
{
    // cout << fun(24) << endl;
    // 使用非递归的动态规划
    int v[] = {1, 3, 5};
    minFetch(v, 3, 24);
    return 0;
}